package hwThree5;

import java.util.ArrayList;

public class LinearProbingHashST<Key, Value> {
    private int n;           // 键值对数量
    private int m = 16;      // 哈希表容量
    private Key[] keys;      // 键数组
    private Value[] values;  // 值数组

    public LinearProbingHashST() {
        keys = (Key[]) new Object[m];
        values = (Value[]) new Object[m];
    }

    public LinearProbingHashST(int capacity) {
        m = capacity;
        keys = (Key[]) new Object[m];
        values = (Value[]) new Object[m];
    }

    // 哈希函数
    private int hash(Key key) {
        return (key.hashCode() & 0x7fffffff) % m;
    }

    // 调整大小
    private void resize(int capacity) {
        LinearProbingHashST<Key, Value> temp = new LinearProbingHashST<>(capacity);
        for (int i = 0; i < m; i++) {
            if (keys[i] != null) {
                temp.put(keys[i], values[i]);
            }
        }
        keys = temp.keys;
        values = temp.values;
        m = temp.m;
    }

    // 插入键值对（允许重复键）
    public void put(Key key, Value value) {
        if (n >= m / 2) resize(2 * m); // 如果使用率超过50%，扩容

        int i;
        for (i = hash(key); keys[i] != null; i = (i + 1) % m) {
            // 不检查键是否重复，直接跳过
        }
        keys[i] = key;
        values[i] = value;
        n++;
    }

    // 获取键所关联的任意值
    public Value get(Key key) {
        for (int i = hash(key); keys[i] != null; i = (i + 1) % m) {
            if (keys[i].equals(key)) {
                return values[i]; // 返回找到的第一个值
            }
        }
        return null; // 找不到键
    }

    // 删除表中所有与给定键相等的键值对
    public void delete(Key key) {
        ArrayList<Integer> indicesToDelete = new ArrayList<>();

        // 找到所有与 key 匹配的索引
        for (int i = hash(key); keys[i] != null; i = (i + 1) % m) {
            if (keys[i].equals(key)) {
                indicesToDelete.add(i);
            }
        }

        // 删除这些键值对
        for (int index : indicesToDelete) {
            keys[index] = null;
            values[index] = null;
            n--;
        }

        // 重新整理哈希表
        if (n > 0 && n <= m / 8) resize(m / 2); // 如果使用率低于12.5%，缩容
        rehash();
    }

    // 检查键是否存在
    public boolean contains(Key key) {
        return get(key) != null;
    }

    // 重新整理哈希表
    private void rehash() {
        LinearProbingHashST<Key, Value> temp = new LinearProbingHashST<>(m);
        for (int i = 0; i < m; i++) {
            if (keys[i] != null) {
                temp.put(keys[i], values[i]);
            }
        }
        keys = temp.keys;
        values = temp.values;
        m = temp.m;
    }

    // 返回键值对数目
    public int size() {
        return n;
    }

    // 检查是否为空
    public boolean isEmpty() {
        return size() == 0;
    }

    // 测试代码
    public static void main(String[] args) {
        LinearProbingHashST<String, Integer> st = new LinearProbingHashST<>();

        // 插入键值对（包含重复键）
        st.put("A", 1);
        st.put("B", 2);
        st.put("A", 3);
        st.put("C", 4);
        st.put("A", 5);

        // 获取键值
        System.out.println("Get A: " + st.get("A")); // 可能返回 3 或 5（任意值）
        System.out.println("Get B: " + st.get("B")); // 返回 2

        // 删除键值对
        st.delete("A");
        System.out.println("Contains A? " + st.contains("A")); // false
        System.out.println("Contains B? " + st.contains("B")); // true

        // 检查大小
        System.out.println("Size: " + st.size()); // 2
    }
}